Sequence Alignments

Overview

After completing this session, students should be able to:

• Practice global Needleman Wunsch algorithm in their notebook

• Align a sequence

• Download R

  • Interact with the R Console

• Download and align SARS-CoV-2 sequences from the State of Bahia, Brazil

Sequence alingnments: Global Alignment

1) Designing an algorithm: describe in human language

• Describe what needs to be done in human language
• What the problem is
  • For global alignment: to align two whole sequences against each other to evaluate how much similar they are
  • Compare nucleotide by nucleotide, what the identity match is or is not
  • Account for nucleotides that have the same or different identities

Sequence alingnments: Global Alignment

1) Designing an algorithm: describe in human language

• Needlemand-Wunsch algorithm
  • Alignment of the entire sequence
  • Match, mismatch and gap penalty score
  • Saul Ben Needleman and Christian Dennis Wunsch proposed the algorithm in 1970.

Sequence alingnments: Global Alignment

1) Designing an algorithm: describe in human language

• https://www.youtube.com/watch?v=18vt6k-2Jbs
• https://www.youtube.com/watch?v=FIxYGV7WPA8
• https://www.slideshare.net/HarshitaBhawsar/needlemanwunch-algorithm-harshita

Sequence alingnments: Global Alignment

1) Human language: Goals of Sequence Alignments

• Goals of the alignment
  • Measure similarity
  • Observe patterns of sequence conservation between related biological species and variability of sequences over time and geographic location
  • Infer evolutionary relationships

Sequence alingnments: Global Alignment

ALGORITHM

Sequence alingnments: Global Alignment

1) Human language: Goals of Sequence Alignments

• Steps:

  • 1. Initialization
  • 2. Matrix fill or scoring
  • 3. Traceback and alignment

Sequence alingnments: Global Alignment

2) Pseudocode: Use equations and numbers that describe the calculations for the algorithm

• Rules:
  • Fill the first column and the last row with gap values
  • Value of box beside + Gap value
  • Value of box bottom + Gap value
  • Diagonal value + {match/mismatch}

Sequence alingnments: Global Alignment

• Let’s see an example.

• Align two sequences in the notebook

  • GATC (sequence 1)
  • GAGC (sequence 2)

Sequence alingnments: Global Alignment

Initialization

• In your notebook, please create columns to align two sequences

Sequence alingnments: Global Alignment

Matrix Fill

• Fill first row and first column.

Sequence alingnments: Global Alignment

Matrix Fill

• Fill first row and first column (continued).

Sequence alingnments: Global Alignment

Matrix Fill

• Fill first cell.

Sequence alingnments: Global Alignment

Matrix Fill

• Fill second row.

Sequence alingnments: Global Alignment

Matrix Fill

• Fill all cells.

Sequence alingnments: Global Alignment

2) Pseudocode: Continuing the procedure

Sequence alingnments: Global Alignment

2) Pseudocode: Implementation (not using code) of the Needlemand-Wunsch Scoring Matrix

• For the Traceback step, we follow the pointers (the arrows)

Sequence alingnments: Global Alignment

3) Traceback: alignment of the Needlemand-Wunsch Matrix

• For the Traceback step, we follow the pointers (the arrows)

Sequence alingnments: Local Alignment

• Smith-Waterman
  • Match +1, Mismatch -1, GAP penalty -2
  • https://www.youtube.com/watch?v=bFDRny7T3_s&t=3s
  • Query sequence vs. database sequence on a character to character level
  • Dinamic programming: divide problems into sub-problems for optimal solution
  • initalization, matrix filling and trace back

Sequence alingnments: Local Alignment

• BLAST

  • http://www.ncbi.nlm.nih.gov/BLAST/

  • Fragment of SARS-CoV-2 sequence to blast:

    • ACAAACCAACCAACTTTCGATCTCTTGTAGATCTGTTCTCTAAACGA

Sequence alignements: the scoring system

Algorithm or Pipeline

• An algorithm can also called a pipeline.

• The first step to develop an algorithm is to objectively explain how to answer a question or solve a problem.

• A Variant Calling algorithm identifies Variants or Mutations in the genome of an organism.

• Also called SNP calling pipeline.

Algorithm or Pipeline

• Here is the pseudocode of a SNP calling pipeline:

  • Align to reference sequence (FASTA)

  • Compare alignment to reference (SAM)

  • Annotate differences (mutations) (VCF)

  • Extract mutations from VCF using script

  • Construct a SNP Frequency Table

Algorithm or Pipeline

• Schematic of a SNP call pipeline

  • The blue boxes indicates the analysis being performed.

  • The text above the boxes indicates the software used for each analysis. Figure is from r-charts (n.d.).

Bioinformatics Software Development

• Software development considers the analytical steps in human language

  • What are the exact steps that are necessary for execution of the analysis?

• Then, the software product considers the steps the machine will execute

• How files are produced and what are the processing steps?

• Where in the computational infra-structure are the files stored?

Bioinformatics Software Development

Conclusions

• We can develop our own computational methods to understand biology and propose solutions

• In order to do that we need to follow these three steps for developing a computational algorithm that will solve a problem:

Bioinformatics Software Development

Conclusions

• 1. Describe the problem in human language and propose solutions in ways that are inteligible to human collaborators
• 2. Start using mathematical equations and figure out a computational language to write code to process data related to a problem
  • For example: the variants of SARS-CoV-2 present in Southern Bahia
• 3. Write a script or code to run computational experiments that demonstrate possibilities to solve or address the problem

References